package algorithm.leetcode.I1to100;

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;


/**
 * 合并区间的套路
 * 先将输入的二维数组按第一位元素升序排列
 * 再执行以下合并逻辑
 * 任意两个区间[a,b], [c,d]必定是下面三种情况之一(不妨设a<=b):
 * CASE1:a<=c<=b<=d,两个区间有较交叉,合并成[a,d]
 * CASE2:a<=c<=d<=b,第一个区间完全包含第二个,合并成[a,b]
 * CASE3:a<=b<c<=d,两个区间相交区域为空,不合并
 *
 */

public class Q56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0])); // 仅这行改变了输入数组,侵入性
        int index = -1;
        int[][] result = new int[intervals.length][2];

        for (int[] interval : intervals) {
            // 如果是刚开始,或者case3,直接添加区间
            if (index == -1 || result[index][1] < interval[0]) result[++index] = interval;
            // case1和2可以合并讨论
            else {
                result[index][0] = Math.min(result[index][0], interval[0]); // 原始的interval已经按第一元素升序了,这行其实可以不要,但是加进来好理解
                result[index][1] = Math.max(result[index][1], interval[1]);
            }
        }
        return Arrays.copyOf(result, index);
    }


    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>((o1, o2) -> o1-o2);
        set.add(1);
        set.add(3);
        set.add(2);
        set.add(5);
        set.add(7);
        System.out.println(set);
        set.add(4);
        System.out.println(set);

    }

}
